import { Node } from './models/linked-list-models';
import { defaultEquals, IEqualsFunction } from '../util';
/**
 * 链表是一个数据元素按照链式存储结构进行存储的一般线性表。它的数据元素
 * 由一个存储元素本身的节点和一个指向下一个元素的引用（指针）组成的。
 *
 * 栈、队列与链表的区别：
 * 在逻辑结构上，他们都具有线性结构也就是线性表特性（有唯一的前驱和后继），
 * 栈和队列属于受限线性表（受限表示对结点的操作受限制），而链表不受限制。
 * 在存储结构上，栈和队列是顺序存储结构，也就是用一组地址连续的存储单元依
 * 次存储线性表中的数据元素；而链表就不一样了，它是链式存储结构，也就是用
 * 一组任意的存储单元存储线性表中的数据元素（可连续也可不连续）。
 */
export default class LinkedList<T> {
    protected count: number; // 链表元素个数
    protected head: Node<T>; // 指向链表中的第一项（链表的首部元素）
    protected equalsFn: IEqualsFunction<T>; // 比较函数
    constructor(equalsFn: IEqualsFunction<T> = defaultEquals) {
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }
    /**
     * 向链表尾部添加元素
     */
    public push(element: T) {
        const node: Node<T> = new Node(element);
        if (this.head == null) { // 链表为空
            this.head = node; // 直接赋值给head
        } else {
            // 优化，直接用getElementAt
            const current = this.getElementAt(this.count - 1);
            node.next = current.next; // 优化，方便形成循环链表
            current.next = node; // 新元素添加到末尾
        }
        this.count ++; // 数量更新
    }
    /**
     * 向链表首部添加元素
     */
    public unshift(element: T) {
        const node: Node<T> = new Node(element);
        if (this.head == null) { // 链表为空
            this.head = node; // 直接赋值给head
        } else {
            node.next = this.head; // 新元素与旧首部元素连接
            this.head = node;
        }
        this.count ++; // 数量更新
    }
    /**
     * 返回链表中特定位置的元素
     */
    public getElementAt(index: number): Node<T> {
        if (index < 0 || index >= this.count) {
            return undefined;
        }
        let current: Node<T> = this.head;
        for (let i = 1; i <= index && current != null; i ++) {
            current = current.next;
        }
        return current;
    }
    /**
     * 向链表中特定位置插入一个新元素
     */
    public insert(element: T, position: number): boolean {
        if (position < 0 || position > this.count) { // 参数不合法
            return false;
        }
        const node: Node<T> = new Node<T>(element);
        if (position === 0) { // 要放到第一个位置
            this.unshift(element);
        } else {
            const current: Node<T> = this.getElementAt(position - 1);
            node.next = current.next; // 将这个位置的元素放到node的next上
            current.next = node; // 再把node放到lastOne的next上，完成连接
            this.count ++; // 数量更新
        }
        return true;
    }
    /**
     * 从链表中移除指定位置的元素
     */
    public removeAt(index: number): T {
        if (this.isEmpty() || index < 0 || index >= this.count) {
            return undefined;
        }
        let result: Node<T> = null;
        if (this.count === 1) { // 特殊情况1：链表只有一个元素
            result = this.head;
            this.clear();
            return result.element;
        }
        if (index === 0) { // 特殊情况2：要删除链表首部元素
            result = this.head;
            this.head = result.next; // 往后挪一个
        } else {
            const lastOne: Node<T> = this.getElementAt(index - 1);
            result = lastOne.next;
            // 将这个位置的下元素放到lastOne的next上，完成连接
            lastOne.next = result.next;
        }
        result.next = undefined;
        this.count --; // 数量更新
        return result.element;
    }
    /**
     * 返回元素在链表中的索引
     */
    public indexOf(element: T): number {
        // 优化，使用size，因为要考虑循环链表
        for (let i = 0, node = this.head; i < this.size()
            && node != null; i ++, node = node.next) {
            if (this.equalsFn(element, node.element)) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 从链表中移除指定元素
     */
    public remove(element: T): T {
        const index: number = this.indexOf(element);
        return this.removeAt(index);
    }
    /**
     * 链表是否为空
     */
    public isEmpty(): boolean {
        return this.count === 0;
    }
    /**
     * 链表大小
     */
    public size(): number {
        return this.count;
    }
    /**
     * 返回链表中的首部元素
     */
    public getHead() {
        return this.head;
    }
    /**
     * 清空
     */
    public clear() {
        this.head = undefined;
        this.count = 0;
    }
    /**
     * 返回链表的字符串展示
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        let current: Node<T> = this.head;
        let objString: string = `${current.element}`;
        for (let i = 1; i < this.size(); i ++) {
            current = current.next;
            objString = `${objString},${current.element}`;
        }
        return objString;
    }
}
